package _11_整理题目._9_高频题目;

import org.junit.Test;

import java.util.*;
import java.util.stream.*;

/**
 * 给定一个数组，找出其中最小的K个数。
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
 * 如果K>数组的长度，那么返回一个空的数组
 * 
 * 初始化一个 大根堆  new PriorityQueue<>( (a,b)->b-a )
 * stream().collect(Collectors.toList())
 * 
 */
public class _02_最小k个数 {
    
    PriorityQueue<Integer> queue1 = new PriorityQueue<>( (a,b) -> b-a);
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    });

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if(k == 0 || k > input.length) return new ArrayList<>();
        
        for(int num : input) {
            if(queue.size() < k) {
                queue.offer(num);
            } else if(queue.peek() > num) {
                queue.poll();
                queue.offer(num);
            }
        }
        
        return (ArrayList<Integer>) queue.stream().sorted().collect(Collectors.toList());
    }
    
    @Test
    public void main() {
        int[] inputs = {4,5,1,6,2,7,3,8};
        ArrayList<Integer> result = GetLeastNumbers_Solution(inputs, 4);
        System.out.println(result);
    }
    
}
